class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        // 对于这道题目首先要理解的就是构造出的最大格子一定是在vector中的
        // 由此我们就能够去进行枚举了
        // 分析一个位置i，我们先获得左边刚好小于i高度的位置为left，那么左边刚好大于等于i高度的位置就是left+1如果不存在填入的是-1
        // 对于i右边设定搞好小于i高度的坐标为right，那么刚好大于等于i位置的左边就是right+1,如果不存在那么填入的就是n
        // 由此就能够求出i位置能够产生的最大居心的面积为(right-left-1)*height[i]
        // 现在的目的就是通过单调栈来求出第i个位置左边和右边最后小于这个位置的高度的最后一个位置
        // 使用单调栈来解决
        int n = heights.size();
        vector<int> left(n,-1);
        stack<int> s;
        for(int i = 0;i<n;i++)
        {
            while(!s.empty()&&heights[s.top()]>=heights[i])
            {
                s.pop();
            }
            if(!s.empty())
            {
                left[i] = s.top();
            }
            s.push(i);
        }//经过这个步骤对于每一个位置i都能够知道左边刚好小于等于我这个元素的最后一个元素的位置了
        //现在去求右边的
        s = stack<int>();
        vector<int> right(n,n);
        for(int i = n-1;i>=0;i--)
        {
            while(!s.empty()&&heights[s.top()]>=heights[i])
            {
                s.pop();
            }
            if(!s.empty())
            {
                right[i] = s.top();
            }
            s.push(i);
        }
        //然后现在就是通过1公式去计算面积了
        int ret = 0;
        for(int i = 0;i<n;i++)
        {
            ret = max(ret,(right[i]-left[i]-1)*heights[i]);
        }//找到最大的面积
        return ret;
    }
};